package pers.sloera.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 得分最高的单词集合
 *
 * @author sloera
 * @date 2023-02-26 10:34:40
 */
class MaximumScoreWordsFormedByLetters {
    public static void main(String[] args) {
        Solution solution = new MaximumScoreWordsFormedByLetters().new Solution();
        solution.maxScoreWords(new String[]{"xxxz", "ax", "bx", "cx"}, new char[]{'z', 'a', 'b', 'c', 'x', 'x', 'x'}, new int[]{4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 10});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxScoreWords(String[] words, char[] letters, int[] score) {
            // 每个单词，会消耗多少letter
            List<Map<Integer, Long>> wordRestrict = new ArrayList<>();
            // 每个位置的单词，能得到多少分
            List<Integer> wordScore = Arrays.stream(words).map(word -> {
                //  get word score
                wordRestrict.add(word.chars().boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting())));
                return word.chars().map(x -> x - 'a').map(x -> score[x]).sum();
            }).collect(Collectors.toList());
            // 遍历每一个 wordScore 和 wordRestrict，取最大的值
            // 每个word取不取可以用bit来表示，相当于有 2^n 的状态
            System.out.println();
            int max = 0;
            for (int i = 1; i < (int) Math.pow(2, wordScore.size()); i++) {
                if (restrictMatch(wordRestrict, i, letters)) {
                    max = Math.max(max, countScore(wordScore, i));
                }
            }
            return max;
        }

        private int countScore(List<Integer> wordScore, int state) {
            int sum = 0;
            for (int i = 0; i < wordScore.size(); i++) {
                if (isPick(i, state)) {
                    sum += wordScore.get(i);
                }
            }
            return sum;
        }

        private boolean restrictMatch(List<Map<Integer, Long>> wordRestrict, int state, char[] letters) {
            Map<Integer, Long> letterRestrict = String.valueOf(letters).chars().boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
            for (int i = 0; i < wordRestrict.size(); i++) {
                if (isPick(i, state)) {
                    for (Map.Entry<Integer, Long> restrictEntry : wordRestrict.get(i).entrySet()) {
                        long restrictLeft = letterRestrict.getOrDefault(restrictEntry.getKey(), 0L) - restrictEntry.getValue();
                        if (restrictLeft < 0) {
                            return false;
                        }
                        letterRestrict.put(restrictEntry.getKey(), restrictLeft);
                    }
                }
            }
            return true;
        }

        private boolean isPick(int index, int state) {
            return (1 << index & state) != 0;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}
